Corelab Seminar
2021-2022
Georgios Amanatidis
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
Abstract.
We consider the problem of fairly allocating a set of
indivisible goods to a set of strategic agents with additive valuation
functions. We assume no monetary transfers and, therefore, a mechanism
in our setting is an algorithm that takes as input the reported-rather
than the true- values of the agents. Our main goal is to explore whether
there exist mechanisms that have pure Nash equilibria for every instance
and, at the same time, provide fairness guarantees for the allocations
that correspond to these equilibria. We focus on two relaxations of
envy-freeness, namely envy-freeness up to one good (EF1), and
envy-freeness up to any good (EFX), and we positively
answer the above question. In particular, we study two algorithms that
are known to produce such allocations in the non-strategic setting:
Round-Robin (EF1 allocations for any number of agents) and a
cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of
Discrete Mathematics, 2020] (EFX allocations for two agents). For
Round-Robin we show that all of its pure Nash equilibria induce
allocations that are EF1 with respect to the underlying true values,
while for the algorithm of Plaut and Roughgarden we show that the
corresponding allocations not only are EFX but also satisfy maximin
share fairness, something that is not true for this algorithm in the
non-strategic setting! Further, we show that a weaker version of the
latter result holds for any mechanism for two agents that always has
pure Nash equilibria which all induce EFX allocations.
Joint work with Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, και Rebecca Reiffenhäuser